package leetcode.editor.cn.q1_300.q50;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author qidi
 * @date 2021-12-09 14:20:11
 */
class Q0056_MergeIntervals {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[][] merge(int[][] intervals) {
            if (intervals.length == 1) return intervals;

            Arrays.sort(intervals, Comparator.comparingInt((int[] arr) -> arr[0]));

            int size = intervals.length;
            int i = 0;
            int j = 1;
            while (j < intervals.length) {
                if (intervals[i][1] >= intervals[j][0]) {
                    intervals[i][1] = Math.max(intervals[j][1], intervals[i][1]);
                    intervals[j][0] = -1;
                    size--;
                } else {
                    i = j;
                }
                j++;
            }

            int[][] res = new int[size][2];
            int n = 0;
            int k = 0;
            while (k < size && n < intervals.length) {
                if (intervals[n][0] != -1) {
                    res[k] = intervals[n];
                    k++;
                }
                n++;
            }
            return res;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0056_MergeIntervals().new Solution();
        int[][] ints = solution.merge(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}});
        for (int i = 0; i < ints.length; i++) {
            System.out.print(Arrays.toString(ints[i]));
        }
        System.out.println();

        ints = solution.merge(new int[][]{{1, 3}, {2, 11}, {6, 10}, {15, 18}});
        for (int i = 0; i < ints.length; i++) {
            System.out.print(Arrays.toString(ints[i]));
        }
        System.out.println();
    }
}